package leetcode.dynamic_programming;

import java.util.Arrays;

/**
 * 递归实现斐波那契数列的计算和非递归实现以及使用记忆化搜索方式进行实现。
 * 重叠子的存在使得计算每次都会多计算
 */
public class Fibonacci {
    private int num = 0;

    /**
     * 递归实现
     *
     * @param n
     * @return
     */
    public int fun1(int n) {
        num++;
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }

        return fun1(n - 1) + fun1(n - 2);
    }

    /**
     * 使用记忆化搜索的方式进行解决
     * 定义一个数组，用来存放0-n 上 sum[n]对应的值
     *
     * @param n
     * @return
     */


    public int fun2(int n) {
        int[] sum = new int[n + 1];
        Arrays.fill(sum, -1);
        return fun2(n, sum);
    }

    private int fun2(int n, int[] sum) {
        num++;
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        if (sum[n] == -1) {
            sum[n] = fun2(n - 1, sum) + fun2(n - 2, sum);
        }
        return sum[n];
    }


    //使用动态规划思想
    public int fun3(int n) {
        num++;
        int[] sum = new int[n + 1];
        sum[0] = 0;
        sum[1] = 1;

        for (int i = 2; i <= n; i++)
            sum[i] = sum[i - 1] + sum[i - 2];
        return sum[n];
    }

    public int getNum() {
        return num;
    }

    public static void main(String[] args) {

        //int n = 42;
        int n = 40; // 注意: 我们使用n = 1000只是为了测试性能, 实际上会溢出
        // 斐波那契额数列是以指数速度上涨的

        Fibonacci solution = new Fibonacci();
        long startTime = System.currentTimeMillis();
        int res = solution.fun2(n);
        long endTime = System.currentTimeMillis();

        System.out.println("fib(" + n + ") = " + res);
        System.out.println("time : " + (endTime - startTime) + " ms");
        System.out.println("run function fib() " + solution.getNum() + " times.");
    }
}
